package com.my.study.structures.recursion;

/**
 * @author Carlos
 * @version 1.0
 * @Description 八皇后问题
 * <p>
 *      在一个8 * 8的棋盘上，摆放8个皇后，摆放的要求是8个皇后之间不能相互攻击
 *      （在同一列、同一行、同一斜线上会攻击）
 * </p>
 * <p>
 * 使用递归+回溯解决八皇后问题思路：
 *  1、把第一个皇后摆放在第一行的第一列；
 *
 *  2、第二个皇后摆放在第二行第一列，判断是否满足条件，不满足条件就往后放，
 *     判断第三列、第四列...直到满足条件为止；
 *
 *  3、继续摆放第三个皇后，还是从第一列、第二列....直到第8个皇后也能放在一个满足条件的位置，
 *  这算是找个其中一个正确解；
 *
 *   4、当得到一个正确解后，开始回溯：从最后一行移动皇后位置，没有满足的，回退到上一个栈，即将第一个皇后放在第一行
 *  所有正确解全部得到；
 *
 *  5、然后继续把第1个皇后放在第一行第二列， 后面继续1、2、3、4的步骤....
 *
 * 说明：
 * 理论上八皇后问题需要使用二维数组构建棋盘，但是可以通过约定和算法使用一维数组解决问题，例如：
 * </p>
 *
 *  arr[8] = {0,4,7,5,2,6,1,3} arr下标index表示第几行/第几个皇后(index+1)，
 *  arr[index]=val表示第index+1个皇后在第val+1列    ==> 数据下标表示行 值表示列
 *
 *
 * @date 2021/7/5 22:40
 **/
public class EightQueens {

    private static final int MAX = 8;
    private static int[] arr = new int[MAX];

    private static int count = 0;
    private static int checkClashCount = 0;

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.place(0);
        System.out.println("==============正确解法数============");
        System.out.println(count);
        System.out.printf("判断冲突次数%d", checkClashCount);
    }


    /**
     * 放置第n个皇后
     *
     * @param n n从0开始，当n=8时，表明8个皇后放置好了
     */
    private void place(int n) {
        if (n == MAX) {
            out();
            return;
        }
        // 依次放入皇后， 并判断是否冲突
        for (int i = 0; i < MAX; i++) {
            // 先把当前皇后，放到该行的第1列
            arr[n] = i;
            // 判断当放置第n个皇后到i列时，是否冲突
            if (!checkClash(n)) {
                // 不冲突
                place(n+1);
            }
            // 如果冲突，就继续执行arr[n] = i;即将第n个皇后在本行 后移一个位置
        }
    }


    /**
     * 检查摆放第n个皇后时，是否与前面的皇后冲突了
     *
     * @param n 表示第n个皇后
     * @return true:冲突 false:不冲突
     */
    private static boolean checkClash(int n) {
        checkClashCount++;
        for (int i = 0; i < n; i++) {
            // 1.arr[i] == arr[n]，表示是否为同列
            // 2.Math.abs(n-i) == Math.abs(arr[n] - arr[i])，表示是否为同一斜线（同一斜线，行 - 行 = 列 - 列）
            // 3.同行没有必要判断，因为n肯定是自增的
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[n] - arr[i])) {
                return true;
            }
        }
        return false;

    }


    private static void out() {
        count++;
        for (int i = 0; i < MAX; i++) {
            System.out.print(arr[i] + "");
        }
        System.out.println();
    }

}
